package design;

import java.util.Scanner;

public class getSmallSum {

    // 暴力方法 O(N^2)
    public static long  smallSum(int[] arr){
        long sum = 0;
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]){
                    sum+=arr[j];
                }
            }
        }
        return sum;
    }
    public static int count = 0;
    public static   int  smallSum2(int[] arr){
        count = 0;
        mergeSort(arr, 0, arr.length-1);
        return count;
    }


    public static void mergeSort(int[] arr, int low, int high){
        if(low == high) return;
        // 计算mid的位置
        int mid = low + (( high - low ) >> 1); // 这样可以避免溢出，而且使用了位运算，效率更高
        mergeSort(arr, low, mid);
        mergeSort(arr, mid+1, high);
        merge(arr, low, mid, high);
    }
    // 归并两个有序的数组
    public static void merge(int[] nums, int left, int mid, int right){
        //定义一个临时数组
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid+1;
        int t = 0;
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                count += nums[i] * ( right - j + 1);
                temp[t++] = nums[i++];
            }else{
                temp[t++] = nums[j++];
            }
        }
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        while(j <= right){
            temp[t++] =nums[j++];
        }
        for(int k =0; k< temp.length;k++){
            nums[left+k] = temp[k];
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i <n; i++){
            arr[i] = scanner.nextInt();
        }
        long sum =  smallSum2(arr);

        System.out.println(sum);

    }



}
